P2114 [NOI2014]起床困难综合症

LOJ也有，巧妙的位运算贪心题

题解：

注意到每一位都是各自独立的，这意味着贪心是可行的

由于每一位在确定了起始的数字后都无法再改变，所以不妨预处理出每一位的0/1在经过所有门后是0还是1

具体的方法是分别拿一个全0的数和一个全1的数（0x7fffffff）去穿过所有门

这样一来对于每一位只会有四种情况：

贪心的，我们从高到低枚举各位，对于第i位，如果能从0变1，那肯定选0，没有代价，贡献为$2^i$

否则，如果只有1能变1，且还有至少$2^i$的资本，那就要用$2^i$的代价换$2^i$的贡献，具体的，“资本”就是指题目给出的m

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

int p1=0x7fffffff,p0,n,m,ans,x; //p1是全1数，p0是全0数
char s[5];

signed main(){
    read(n);read(m);
    while(n--){
        scanf("%s",s);read(x);
        if(s[0]=='A') p0&=x,p1&=x; //分别穿过n道门
        if(s[0]=='X') p0^=x,p1^=x;
        if(s[0]=='O') p0|=x,p1|=x;
    }
    for(int i=29;i>=0;i--){
        if(p0>>i&1) ans|=1<<i; //能从0到1
        else if(p1>>i&1&&(1<<i)<=m) ans|=1<<i,m-=1<<i; //能从1到1且资本充足
    }
    write(ans);
}